Dynamic Network Flows - Chapter 4: The Vickrey Queuing Model

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\coloniff}{:\iff} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\SMid}{\,\middle|\,} \newcommand{\set}[1]{\{#1\}} \newcommand{\sMid}{\,|\,} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\deriv}[2][]{\partial_{#1} #2} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\cexittime}[1][e]{A_{#1}} \newcommand{\network}{N} \newcommand{\tauPmin}{\tau_{p_{\min}}} \newcommand{\fvals}[1]{\mathrm{value}(#1)} \newcommand{\fval}[1]{\mathrm{value}(#1)} \newcommand{\ccaps}[1]{\mathrm{capacity}(#1)} \newcommand{\fcosts}[1]{\mathrm{cost}(#1)} \newcommand{\edgesFrom}[1]{\delta^+(#1)} \newcommand{\edgesTo}[1]{\delta^-(#1)} \newcommand{\PathSet}{\mathcal{P}} \newcommand{\CycleSet}{\mathcal{C}} \)

Lemma 4.3: The following are equivalent for $f_e = (f^+_e,f^-_e)$:

$f$ is a Vickrey flow, i.e. $\ql(0)=0$ and $f^-_e(\theta+\tau_e) = \begin{cases}\nu_e, &\text{if } \ql(\theta) > 0 \\ \min\set{f^+_e(\theta),\nu_e}, &\text{else } \end{cases}$ f.a.a. $\theta \in \IRnn$
$f$ satisfies $\ql(0)=0$ and $\deriv{\ql}(\theta) = \begin{cases} f^+_e(\theta) - \nu_e, &\text{ if } \ql(\theta) > 0 \\ \max\set{f^+_e(\theta) - \nu_e,0}, &\text{ else} \end{cases}$ f.a.a. $\theta \in \IRnn$
$f$ satisfies weak flow-conservation, respects the capacity and satisfies $F^-_e(\theta+\tau_e) = F^+_e(\bar\theta)+(\theta-\bar\theta)\nu_e$ for all $\theta \in \IRnn$ where $\bar\theta \coloneqq \max\set{\theta' \leq \theta \sMid \ql(\theta')=0}$
$f$ satisfies $F^-_e(\theta+\tau_e) = \min\set{F^+_e(\theta')+(\theta-\theta')\nu_e \sMid \theta' \leq \theta}$
$f$ satisfies weak flow-conservation, respects the capacity and satisfies $F^-_e(\cexittime(\theta)) = F^+_e(\theta)$ for all $\theta \in \IRnn$

Lemma A.6: For $G: \IRnn \to \IR$ absolutely continuous with $G(0)=0$, the following are equivalent:

$G(\theta) \geq 0$ for all $\theta \in \IRnn$
$G(\theta) \lt 0 \implies \deriv{G}(\theta) \geq 0$ for almost all $\theta \in \IRnn$
$G(\theta) \leq 0 \implies \deriv{G}(\theta) = 0$ for almost all $\theta \in \IRnn$

Lemma A.5: For $f: \IR \to \IRnn$ locally integrable and $\set{[a_j,b_j)}_{j \in J}$, the following are equivalent:

For every $j \in J$: $f(\theta)=0$ for almost all $\theta \in [a_j,b_j)$
$f(\theta) = 0$ for almost all $\theta \in \bigcup_{j \in J}[a_j,b_j)$

Lemma 4.4: For any $f^+_e: \IR \to \IRnn$ loc.-int. with $\supp(f^+_e) \subseteq \IRnn$ there exists a $f^-_e$ such that $(f^+_e,f^-_e)$ is a Vickrey flow.

Lemma 4.5: $(f^+_e,f^-_e)$ and $(g^+_e,g^-_e)$ two Vickrey flows with $f^+_e(\theta) = g^+_e(\theta)$ f.a.a. $\theta \leq T$. Then, $f^-_e(\theta) = g^-_e(\theta)$ f.a.a. $\theta \leq \cexittime(T)$.

Lemma 4.7: The (Vickrey-)edge loading mapping \[\Phi_e^T: \set{f^+_e \in L^2(\IR) \sMid \supp(f^+_e) \subseteq [0,T], f^+_e \geq 0} \to L^1_{\mathrm{loc}}(\IR), f^+_e \mapsto f^-_e \text{ s.th. } (f^+_e,f^-_e) \text{ is Vickrey flow}\] is sequentially weak-weak-continuous.